647. 回文子串 | Mkdir700的算法笔记

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

输入的字符串长度不会超过 1000 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindromic-substrings

思路及算法

什么是回文串？

一个字符串从左往右和从右往左都是一样，则这个字符串是『回文字符串』

例如： aba ，从右往左依然是aba

注: 一个字符，也是回文串

怎么判断回文串？

相关题目： 9. 回文数

如果字符串长度为1，则它就是『回文串』
如果字符串长度为2，两个字符相同，则它就是『回文串』，例如 aa
如果字符串长度大于2
- 首尾字符相同以及中间部分的字符串是『回文串』，则它就是『回文串』，例如aba，首尾字符串相同(a)并且中间字符b也是回文串
- 首尾字符串相同，中间字符(串)不是回文串，则不是『回文串』，例如 abca
- 首尾字符不相同，不是『回文串』

通过上面的分析，主要就是在字符串大于2的情况，现在我们就来解决这种情况

首先，我们需要判断首尾元素，可以想到『双指针』

让指针i遍历整个字符串[0 ... len(s)]

另一个指针j遍历[0 ... i]

双指针遍历动图演示

根据动图可知，我们需要判断的就是 [j ... i] 这个字符串是不是『回文串』，则需要知道 [j+1 ... i-1]是不是『回文串』，所以我们建立『dp矩阵』，来保存『回文状态』

举个具体的例子[a, b, a]

长度等于1

当i为0，j为0时，此时[j ... i]表示是一个字符a，所以它是回文串，在dp[i][j]的状态为True

(i = 1, j = 1) 和 (i = 2, j = 2) 同理

长度大于2

当i走到2， j为0，此时 [j ... i] 表示的字符串就是 aba

首先判断下这个字符串的长度(length = i - j + 1)，大于2
然后判断s[i] == s[j]，首尾字符是否相等，结果是相等的
接着判断 j 与 i 中间的字符串是不是『回文串』，也就是判断[j+1 ... i-1]是不是『回文串』，因为在之前的遍历中做过判断并将状态保存在了 dp矩阵 中，所以可以直接访问dp[i-1][j+1]。
满足所有条件，就是『回文串』并将当前字符串的『回文状态』保存至dp矩阵中 dp[i][j] == True

同样的方法可以用来解决5. 最长回文子串，赶快动手试试吧

代码

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False]*n for _ in range(n)]
        ans = 0
        
        # 为了代码直观看到双指针遍历过程，这里用的两个while
        # 可以换成双for
        # for i in range(n):
        # 	for j in range(i+1):
        i = 0
        while i < n:
            j = 0
            while j <= i:
                length = i - j + 1
                # 长度为1，必定为回文串
                if length == 1:
                    dp[i][j] = True
                    ans += 1
                # 长度为2，首尾字符相同，则为回文串
                elif length == 2 and s[i] == s[j]:
                    dp[i][j] = True
                    ans += 1
                # 长度大于3，首尾字符相同，中间字符串为回文串，则为回文串
                elif length > 2 and s[i] == s[j] and dp[i-1][j+1] == True:
                    ans += 1
                    dp[i][j] = True
                j += 1
            i += 1                
        return ans